//给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。 
//
// 返回 s 所有可能的分割方案。 
//
// 示例: 
//
// 输入: "aab"
//输出:
//[
//  ["aa","b"],
//  ["a","a","b"]
//] 
// Related Topics 深度优先搜索 动态规划 回溯算法 
// 👍 533 👎 0
#include <iostream>
#include <vector>
#include <stack>

using namespace std;


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    vector<vector<int>> f;
    vector<vector<string>> res;
    vector<string> ans;

    void dfs(const string& s,int i){
        if (i == s.size()){
            res.push_back(ans);
            return;
        }
        for (int j = i; j < s.size(); ++j) {
            if (isPalindrome(s, i , j) == 1){
                ans.push_back(s.substr(i, j - i + 1));
                dfs(s,i + 1);
                ans.pop_back();
            }
        }
    }
    //f[i][j] = 0未搜索，1 回文 -1 不是回文 i，j双指针
    int isPalindrome(const string& s,int i ,int  j){
        if (f[i][j]){
            return f[i][j];
        }
        if (i >= j){
            return f[i][j] = 1;
        }
        return f[i][j] = (s[i] == s[j] ? isPalindrome(s,i + 1,j - 1) : -1);
    }
    vector<vector<string>> partition(string s) {
        f.assign(s.size(),vector<int>(s.size()));
        dfs(s,0);
        return res;
    }
};
//leetcode submit region end(Prohibit modification and deletion)
